package 堆;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {
    public int[]elem;
    public int UsedSize;
    public TestHeap(int x) {
         elem = new int[x];
    }
    public void initElem(int[]array) {
        for (int i = 0; i < array.length; i++) {
          if(isFUll()) {
             elem= Arrays.copyOf(elem,elem.length*2);
          }
            elem[i]=array[i];
            UsedSize++;
        }
        createHeap();
    }
    public void createHeap(){
        for (int parent = (UsedSize-1-1)/2; parent >=0 ; parent--) {
            shiftDown(parent,UsedSize);
        }
    }
    /**
     * 父亲下标和每棵树的结束下标
     * @param parent
     */
    //大根堆
    private void shiftDown(int parent,int len) {
        int child=2*parent+1;
        while (child<len) {
          if(child+1<len && elem[child]<elem[child+1]) {
              child++;
          }
          //子节点大于父亲节点就交换
          if(elem[child]>elem[parent]) {
              swap(elem,parent,child);
              parent=child;
              child=2*parent+1;

          }else {
              break;
          }
        }
    }
    private void swap(int[]array,int left,int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
    //插入、
    public void offer(int val) {
        if(isFUll()) {
          elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[UsedSize++]=val;
        shiftUp(UsedSize-1);
    }
    //向上调整
    public void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child != 0) {
            //子节点大于父亲节点
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
            }else {
                break;
            }
            child = parent;
            parent = (parent-1)/2;
        }
    }

    /**
     * 删除
     * @return
     */
    public int pop() {
        if(isEmpty()) {
            return -1;
        }
        int tmp = elem[0];
        swap(elem,0,UsedSize-1);
        UsedSize--;
        shiftDown(0,UsedSize);
        return tmp;
    }

    /**
     * 获取前k个最大值
     * @return
     */
    public int[] bigK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //比较，比堆顶元素大的入堆
        //小根堆，堆顶元素是最小值
        //比堆顶元素小说明比堆里的任何元素都小
        //比堆顶元素大，说明可以把此时的堆顶弹出
        for (int i = k; i < arr.length; i++) {
            if(priorityQueue.peek()<arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        int[]elem1 = new int[k];
        for (int i = 0; i < k; i++) {
            elem1[i]=priorityQueue.poll();
        }
        return elem1;
    }

    /**
     * 获取前k个最小值
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(k,new IntCmp());
        int[]elem1 = new int[k];
        if(k==0 || arr == null) {
            return elem1;
        }
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //比较，比堆顶元素小的入堆
        //因为是大根堆，堆顶元素最大，如果比堆顶元素还要大，那就说明比堆里的k个元素都要大
        //因为求的是前k个最小值，所以只有比堆顶元素小的值才能进，并且弹出堆顶
        for (int i = k; i < arr.length; i++) {
            if(priorityQueue.peek()>arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            elem1[i]=priorityQueue.poll();
        }
        return elem1;
    }
    public boolean isEmpty() {
        return elem.length==0;
    }
    public boolean isFUll() {
        return UsedSize==elem.length;
    }

    /**
     * 时间复杂度：O(Nlog(n))
     * 空间复杂度：O(1)
     * @param array
     */
    public void  HeapSort(int[]array) {
       //建立大根堆
        initElem(array);
        int end=UsedSize-1;
        while (end>0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }

    }
}
class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
